【每日算法】基础算法——快速排序[第k个数]（二）

题目内容

给定一个长度为n的整数数列，以及一个整数k，求出数列从小到大排序后的第k小的数。

输入格式

第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在1~10^9范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第k小数。

数据范围

1≤n≤100000,
1≤k≤n

输入样例

5 3
2 4 1 5 3

输出样例

3

题解

基于前一讲的快排思路，若将整个数列划分为两个区间后，假设前一个区间的数个数为S1，后一个区间的数的个数为S2，那么和k比较，能够确定第k小的数属于其中哪个区间。所以，只需要递归对应区间中的数即可。不过这里需要注意的是，如果确定在第二个区间的话，那么全局第k小的数在第二个区间对应的是第k-S1的数。然后根据之前的步骤进行递归求出最终的结果。

代码实现

#include <iostream>
using namespace std;

const int N = 100010;

int n,k;
int q[N];

int quick_sort(int l, int r, int k){
    if (l==r) return q[l];
    int x = q[l],i=l-1,j=r+1;
    while(i<j){
        while(q[++i]<x);
        while(q[--j]>x);
        if (i < j) swap(q[i],q[j]);
    }
    int sl=j-l+1;
    if (k<=sl) return quick_sort(l,j,k);
    else return quick_sort(j+1,r,k-sl);
}

int main(){
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> q[i];
    cout << quick_sort(0,n-1,k) << endl;
    return 0;
}

这里是原题链接